A basic function required of a typical communication network is one of routing a service request through the network and then establishing a connection between an originating point and a destination point according to the route selected. In the terminology of telephony, this activity is often described as a calling party placing a call to a called party. The call is established on a path through the network designated a route. In turn, a route may be comprised of one or more intermediate points or nodes interconnected to other nodes by one or more links or trunk groups comprising servers or trunks. Examples of such networks are the intra-LATA (Local Access and Transport Area) telephone network and the interLATA (that is, long distance) telephone network.
It occasionally happens that the traffic, e.g., the call, is blocked either involuntarily or voluntarily. An involuntary blocking occurs when no route through the network can be found which has at least one free trunk in all the trunk groups. A voluntary blocking occurs when, even though an available route can be found, the call is blocked to protect future call attempts. A voluntary blocking may be indicated when the only available routes all go over two or more trunk groups, with a sizable risk that carrying one more call now will lead to multiple call blockings in the near future.
Traffic routing is evolving from time-invariant, hierarchical schemes to time-dependent, non-hierarchical schemes. In the first scheme, a routing plan with a hierarchical ranking of nodes is employed. In the telephone environment, these nodes may also be considered as switching centers since the nodes are implemented with switches. The highest ranking center has been designated a regional center (RC) followed in rank order by a sectional center (SC), a primary center (PC) and a toll center (TC). Each RC has one or more SCs homing on it; each PC homes on an RC or SC and has one or more TCs homing on it. Under this plan, any center homes on another center of higher rank within the same region but not on a center of lower rank. Time-invariant, hierarchical routing through such a network is effected by progressive routing (PR).
To describe briefly progressive routing and, shortly, other conventional schemes, a simplified hierarchical network is considered. In this illustrative network, a first PC (PC1) and a second PC (PC2) are directly connected; similarly, a first TC (TC1) connects to a second TC (TC2). Moreover, TC1 homes on PC1 and TC2 homes on PC2; TC1 is also connected to PC2 by a direct trunk group and, similarly, TC2 is connected to PC1 by a direct trunk group. The trunk groups (TG) interconnecting the various centers are designated by: TG1 links TC1 and TC2; TG2 links TC1 and PC2; TG3 links TC2 and PC2; TG4 links TC1 and PC1; TG5 links TC2 and PC1; and TG6 links PC1 and PC2. The call under consideration is to be routed from TC1 to TC2.
There are four possible routes between TC1 and TC2 defined as follows: the first route (R1) is composed of TG1; R2 includes TG2 and TG3; R3 comprises TG4 and TG5; and R4 comprises TG4, TG6 and TG3. In this progressive routing example, the first route considered, as required by the hierarchical ranking, is R1. If TG1 has a non-blocking status, the call is established over TG1. However, if TG1 is blocked, then R2 is considered next. If TG2 is free, routing control is passed from TC1 to PC2, without regard to the blocking status of TG3, the next link in R2. If TG3 is blocked, the calling party is given a network congestion signal indicative of a blocked route. With progressive routing, R3 or R4 is never tested if TG2 of R2 is free. In this example, it may have been possible to route the call over R3 if the status of each trunk group in R2 was known to TC1. With progressive routing, the routes between originating and destination points are not considered globally, but rather are treated on a local, step-by-step basis. Consideration on a local basis has, in part, been dictated by communication and signaling limitations imposed on the nodes.
With the present availability of stored program control (SPC) and so-called Common Channel Signaling (CCS) systems, communication among the various centers may now be effected without regard to hierarchy. One such routing method which advantageously utilizes the properties of SPC and CCS is disclosed in U.S. Pat. No. 4,345,116, issued Aug. 17, 1982. The subject matter of this reference, described as a dynamic, non-hierarchical routing (DNHR) scheme, is one example of time-dependent, non-hierarchical techniques.
As disclosed in the reference, the methodology controls the generation of a sequence of routes between a source node or switching point and a terminating node or switching point, each route choice being generated without regard to any network hierarchy. Each route, however, is generated in response to traffic demands during predetermined intervals and is subject to a grade of service constraint. That is, the selected sequence is one which is time sensitive and which is so chosen that its use during the specified time interval tends to mitigate the cost of the network that must be provided to meet grade of service. In the notation of the foregoing example, a sequence of routes between TC1 and PC2 for a first time period may be {TG1+TG3; TG2; TG4+TG6}, whereas in another time period the sequence may be {TG4+TG6; TG1+TG3}. If it is required to establish a call from TC1 to PC2 during the first time period, then the sequence associated with the source (TC1) and termination (PC2) nodes for this time period is accessed and processed sequentially by TC1. Thus, the route comprising TG1 and TG3 is selected initially and TC1 requests information, via the CCS network, from node TC2 regarding the blocking status of the pertinent trunk group TG3 terminating on intermediate node TC2. If it is supposed that TG1 is free but TG3 is blocked, then a so-called crankback signal is transmitted to the source node TC1 so the next route in the sequence, namely TG2, may be selected. If TG2 is not blocked, the call would be routed accordingly. This result should be contrasted to the progressive routing scheme; if progressive routing had been used with the sequence of routes under consideration, the call would have been blocked.
In a broad sense, it may be said that the foregoing technique for generating a sequence of routes between node pairs is dynamic in that routing decisions depend on the time of day or week. However, this technique is not truly state dependent. A state dependent routing scheme attempts to minimize call blocking by making, every time a call is attempted, a sophisticated routing decision based not only on the time of the call but also on the numbers of busy and idle trunks in the various trunk groups.
One example of such a state-dependent, dynamic, non-hierarchical routing (SDD) scheme is disclosed in a paper entitled "Dynamic Routing For Intercity Telephone Networks", published in the Proceedings of the Tenth International Teletraffic Congress, June, 1983 and authored by W. H. Cameron, J. Regnier, P. Galloy and A. M. Savoie. An extension to this basic SDD technique is described in another paper entitled "Multihour Dimensioning For A Dynamically Routed Network", published in the Proceedings for the Eleventh International Teletraffic Congress, September, 1985 as authored by R. Huberman, S. Hurtubise, A. LeNir and T. Drwiega.
Another example of a SDD scheme is described in a paper entitled "Use Of A Trunk Status Map For Real-Time DNHR", also published in the Proceedings for the Eleventh International Teletraffic Conqress, September 1985 as authored by G. R. Ash.
To contrast SDD techniques with non-state dependent DNHR networks, the previous example is considered in the SDD context. It is recalled that during the first time period, the sequence {TG1+TG3; TG2; TG4+TG6} was generated. Now, rather than selecting the routes in sequential order, the route which may be selected from the set is the one that contains the largest number of free trunks at the initiation of the call attempt. For instance, if both TG2 and TG3 have, at the same instant, the fewest number of free trunks, then the route selected comprises TG4 and TG6. Other variations on the basic technique are possible. In essence, however, SDD only accounts for the past and present state of the network at the initiation of a call attempt.
All of the previously discussed techniques represent tractable solutions to a very complex optimal control problem with a huge state space. Each solution is based on certain information about the network and certain approximations and, accordingly, departs from the optimal solution. As the solutions progress from PR to DNHR to SDD, more network information is being used. No routing solution, however, accounted for the future state of the network given the past and present states.
The first routing scheme in which the future effect of call-routing is explicitly considered is the state-dependent "separable" routing technique. This technique is the subject matter of our U.S. Pat. No. 4,704,724 issued on Nov. 3, 1987. As disclosed in this patent, a "cost" of adding the (j+1)st call to a trunk group when j calls are already in progress is determined for each trunk group. This cost is a measure of the probable effect of admitting the present call on the blocking of future calls offered to the trunk group. The cost of a multi-link route is the sum of the costs of the trunk groups on the route. When a call arrives, the cost of each potential route is calculated for the current network state, and the call is either carried on the least-cost route, or it is rejected if the cost exceeds the cost of blocking the present call.
The version of the separable routing technique disclosed in our patent makes several approximations in its mathematical model to foster a tractable solution. In particular, the technique utilizes a procedure known as "policy iteration" in the theory of Markov Decision Processes. This name is associated with the following procedure: (i) begin with a "nominal" routing scheme (policy) for which it is feasible to determine the cost associated with different route selections in the network; and (ii) let these nominal costs serve as a guide to the actual selection of routes for each arriving call, thereby producing a new routing scheme or a new policy, which is the result of a "policy iteration" applied to the nominal scheme. The version of separable routing disclosed in our patent was derived from a nominal scheme in which a call blocked on a single route was treated as a lost call. Such a starting point provided excellent call routing capabilities; however, there is room for improvement since optimal performance has not yet been achieved.